This invention relates to a method for decoding information contained in a waveform having a series of peaks which is particularly but not exclusively directed to a method for reading a magnetic stripe that allows the information on the stripe to be read without the need for unidirectional, single stroke swiping motion of the stripe.
The embodiment as disclosed hereinafter which is directed to the primary but not exclusive function of decoding magnetic strip data includes features that permit the accurate decoding of magnetic stripe data in the presence of signal degradations caused specifically, but not exclusively, by variations in the read speed. The embodiment includes the capability to accurately decode stripe data even when the read motion includes stop events (0 read velocity) and reversals.
Prior art US patents in this field are as follows:
U.S. Pat. No. 4,141,494 February 1979 Fisher
U.S. Pat. No. 5,168,275 December 1992 Harrison et al.
U.S. Pat. No. 4,529,872 July 1985 Dinges
U.S. Pat. No. 5,559,317 September 1996 Wong et al.
U.S. Pat. No. 5,912,446 June 1999 Wong et al.
Current magnetic stripe technology is based on F/2F coding (frequency/2 times frequency, also known as Aiken or biphase coding) in which the spatial frequency of flux reversals magnetically encoded on the stripe is used to represent binary information. Spatial frequency F represents a zero bit and spatial frequency 2F represents a one bit. Magnetic stripes are used in many applications, perhaps the most common being on credit or debit cards.
The reading of a magnetic stripe on a card in a situation where the stripe is not read at a suitable speed in a single direction has to date raised significant difficulties. While implementations have been created which operate over wider than typical dynamic ranges, little commercial success has been achieved and none of these implementations are capable of reading over a range of speeds including stop events. Typical magnetic stripe readers require read speeds in excess of 1.5 inches/second. This is particularly a problem where such magnetic stripes are read in a machine that can also read smart cards. Since the smart card reader typically requires a construction that precludes swiping of the card, two options are available. Two individual readers may be used (one for each card type); a solution that is sub-optimal with respect to the amount of space used and potentially confusing for an operator who has to decide which reader to insert a given card into. The other option is to use an insert style reader. Insert style readers, unless motorized, typically suffer low read speeds, card motion stop events and reversals as the card is inserted. A common mode of operation for an insert style combined magnetic stripe/smart card reader (a xe2x80x9chybridxe2x80x9d reader) is to request that the operator perform two different actions, depending on the card type being read. For a smart card, the card is inserted and left in place until the transaction is complete. For a magnetic stripe card, the card is first inserted and then immediately withdrawn. Reading of the magnetic stripe during withdrawal of the card tends to suffer from fewer problems of low card read speed or stops. The card reader is then able to make two read attempts and has a significantly higher probability of successfully reading the stripe. Unfortunately this mode of operation causes significant operator confusion, particularly given the fact that most smart cards also have magnetic stripes. Premature removal of a smart card (before the terminal has completed its communication with the card integrated circuit) can cause significant application problems.
Mechanical means to provide reliable magnetic stripe reads in a hybrid reader, other than using a motor for card transport, have been devised U.S. Pat. Nos. 4,529,872, 5,559,317, 5,912,446. All suffer from significant barriers to commercial success. In particular, they are not easily retrofitable into existing products due to significant mechanical differences from standard practice. They also require a number of precision mechanical components that are expensive to manufacture and assemble, and may lead to product reliability problems.
At least one prior art implementation, U.S. Pat. No. 4,141,494 to Fisher, attempts to deal with the large speed variations encountered when reading stripes moved past a read head by hand. The basic technique employed is to use a special read head to make the read head signal a function of the spatial frequency of the spatially encoded data on the stripe. A significant problem is, once again, changes required to standard practice for the read head making retrofitting to current implementations difficult. The technique also makes use of extensive analogue signal processing which is impractical at the extremely low frequencies encountered leading up to, or away from, a stripe motion stop event.
Prior art in U.S. Pat. No. 5,168,275 has attempted to minimize card read failures due to read signal degradation. While the system disclosed is capable of correcting read errors resulting from magnetic strip degradation, it is not capable of correcting errors caused by variations in read speed or direction. Most of the error correcting features disclosed are also limited to working in a system where the read speed is controlled (motorized reader).
One object of the invention is to provide a method and apparatus for reading data from magnetic stripes with F/2F encoded data.
It is another object of the present invention to provide a reader for a magnetic stripe that can accommodate read signal degradations caused by several factors, including large changes in read velocity as the stripe is moved past a standard inductive read head.
It is yet another object of the present invention to provide a method for digitally capturing the raw stripe read signals in both a memory and computationally efficient manner.
It is still another object of the present invention to provide a method that permits capture of all of the required magnetic stripe signal data in a single pass and also permits minimization of the amount of that data which must be stored at any given time.
These, and other objects, are provided by a method and apparatus for decoding F/2F signals in which samples of the F/2F data signal are repeatedly obtained and are converted into a series of digital values representing typically consistent integrated signal areas (+K or xe2x88x92K volt seconds). The signal area is integrated on a sample by sample basis by forming the integral of the current signal amplitude from which a signal offset has been subtracted. The signal offset is determined by a low pass filtered version of the read signal itself. The cut-off frequency of the filter is set lower than the product of the magnetic stripe encoding density (bits per inch) and the lowest possible stripe read speed (inches per second). The speed referred to is that speed which may be typically encountered in the specific mechanical arrangement associated with the reader (not including stop events). In a specific implementation, all digitally converted samples will either be of area +K or xe2x88x92K, or will be of a maximal time duration based on the limits of the digital representation of the sample duration. The sampled signal is thus converted into digital data that consists of a series of area-duration sample pairs in a novel analogue to digital conversion technique.
Those skilled in the art will recognize that integration of the read signal over a variable period represents filtering over a similarly variable bandwidth. As read speeds increase, the read signal amplitude increases causing the sample duration to decrease. The decrease in sample duration results in an increased filter signal bandwidth. Read signal levels are proportional to read speeds with a standard inductive head, leading to a filter signal bandwidth that exactly tracks the frequency of the read signal.
There is another useful aspect of the variable sample duration and its response to read signal level. With this technique more information is gathered from portions of the signal that contain large amounts of information (peaks), while little information is gathered from portions of the signal that contain little information (gaps between peaks or motion stop events). This aspect has a significant impact on both the computational efficiency and the memory storage requirements of an implementation that supports read speeds with a large dynamic range.
Those skilled in the art will also recognize that the adaptive filter bandwidth, together with the presence of noise, results in changes in the amplitude resolution of the resulting digital samples. Noise may be due to quantization, signal, or device noise. The end result is that the digital samples are of high resolution when the read signal amplitude is low (low read speed) and of lower resolution when the read signal amplitude is high (high read speed). The overall signal to quantization noise ratio is held constant by this mechanism over a large signal dynamic range.
According to another important feature of the invention, the area-duration sample pairs may then be processed in order to detect both the start of a magnetic stripe read and the occurrence of a motion stop event. When no read is being performed the ADC generates samples that are both of sub-threshold area (|area| less than K) and of maximal duration. The start of a magnetic stripe read is detected through the consecutive occurrence of a predetermined number of samples (implementation specific) which are of less than maximal duration. Similarly, a motion stop event is detected through the consecutive occurrence of a predetermined number of samples (implementation specific) which are of maximal duration. After a read has started, the end of the read is determined either through the successful decoding of the entire magnetic stripe, or through detection of a motion stop event which persists beyond a predetermined time duration (may be determined through a specific number of maximal duration samples). Further processing is performed on area-duration samples that have been augmented with indications of the presence of stop events.
According to another important feature of the invention, read signal peaks corresponding to magnetic flux reversals imposed on the read head may be detected through processing of area-duration samples. Sequences of area-duration samples are delineated according to their polarity (positive or negative). A threshold for detection of a peak from these sequences is applied by discarding sequences that do not consist of at least a certain minimum number of samples M. Sequences that pass this test are then analyzed through consideration of all sub-sequences that are of some fraction ( greater than =1/M) of the length of the entire sequence. The total duration of each of these sub-sequences is examined in order to find the sub-sequence with the shortest total duration. This sub-sequence is taken as being representative of the location of the peak and its amplitude. The fact that the shortest sub-sequence corresponds to the maximum in the amplitude of the read signal is a consequence of the ADC technique used. The centre of the sub-sequence in the time domain (half way through its duration) is taken as the time of the peak, while the total area represented by the sub-sequence divided by the total duration of the sub-sequence is taken as the amplitude of the peak. Peaks that do not exceed a specific magnitude are discarded.
Peaks of the same polarity that are separated by a stop event are merged together in order to handle the case where the read head is stopped in a position either directly above, or in the immediate vicinity of, a flux reversal. The number of samples in each sequence representing a peak is adapted at the start of a stripe read by adjusting the K parameter in the ADC. The area of each peak is approximately constant, resulting in the number of samples per peak being inversely proportional to K.
According to another important feature of the invention, various measurements are made of the characteristics of a detected peak. These measurements, called metrics, are calculated based on all of the samples of the sequence in which a peak was detected. These metrics, including for example the total area of the peak, are used to classify each peak into four classes. The classes are defined by the nearest neighbour relationships between the peak in question and the peaks preceding and following it. Peaks in the read signal are generated by flux reversals in an F/2F encoded stripe. There are four possible physical combinations of the immediate neighbourhood of a flux reversal. Each flux reversal is both preceded and followed by a flux reversal either one [F], or one half [2F], bit periods spatially distal. The permutations of these two inter flux reversal distances result in the four possible classes.
Classification of each peak is performed by comparing the match or fit between the metrics for the peak and those of a prototype for each of the four peak classes. The metrics are used with a weighting appropriate to the peak class being evaluated for a match as well as the proximity of stop events. Weighting of the metrics based on these factors facilitates emphasis of the most appropriate metrics in each of the possible cases. For example, metrics which become less reliable near stop events would be weighted less in the match computations for a peak in the vicinity of a stop event. The peak class prototypes are intialized based on a combination of a priori knowledge of the relationships between the metrics for each class, as well as information gathered from the first series of peaks of the stripe read which are known to be of class 0. The prototypes are then adaptively refined throughout the remainder of the read. The classification of each peak results in four confidence values, one for the confidence of a match with each class. Each time a peak is classified, the class prototype which best matches the peak is adapted (trained) to more closely match the metrics of the peak, as long as the confidence of this classification is above a certain threshold. The prototypes for the other classes are also adapted, but with targets calculated from both the peak metric values and the current interrelations between the best match class prototype and the class prototype being adapted.
Following a stop event, the class prototypes are typically poor representations of the peaks in the read signal due to sudden mechanical changes in the read head to magnetic stripe interface. In this event, a number of peaks may be classified with low confidence until the class prototypes become more representative of the actual characteristics of the peaks being read from the stripe. According to the invention, these incidences of low peak classification confidence are mitigated through a xe2x80x9cpeak reverse gap closurexe2x80x9d procedure. Peaks after a stop event are classified until high confidence is obtained on at least a certain number of peak classifications. At this point the class prototypes, which are now representative of the characteristics of the four peak classes, are trained in reverse time sequence backwards through the peaks until the stop event is reached. Peak classification is then re-started from the start of a stop event moving forward in time with the class prototypes that are now good representations of the four peak classes.
According to another important feature of the invention is provided a method of classifying peaks in real time (during the stripe read) conserves memory resources. As peaks are classified with high confidence, their base data (area-duration samples, metric values, etc.) are discarded. When an area of low peak classification confidence is encountered, data required for further analysis is kept only until it is used for that further analysis (peak reverse gap closure, for instance), then it is discarded.
According to another important feature of the invention, classified peaks are decoded into bits using two different algorithms. The most computationally intensive is soft bit classification. Soft bit classification is performed by considering all possible legal sequences (according to F/2F coding rules) of peak classes over a specific window of peaks (3 peaks, for example). The process starts with the assumption that the first peak is on a bit boundary and uses the previously decoded bit value as a constraint. The actual sequence of peaks is considered through the creation of the sum of the confidences that each peak matches the corresponding peak class in the sequence. If, for example, the sequence under consideration was [1, 0, 2], the confidence that this was the best matching sequence would be the sum of the confidence that the first peak was of type 1, the second peak was of type 0, and the third peak was type 2. The confidence of a match with all possible sequences is computed, and the sequence with the highest confidence is selected.
A computationally efficient alternative to soft bit classification is a hard bit classification algorithm. In this algorithm peak classifications are made xe2x80x9chardxe2x80x9d through simply assigning each peak a single class number corresponding to the class with the highest confidence. Matches with the actual peak class sequence are then evaluated by generating a hamming distance between the peak class sequence and all of the legal sequences. If a tie occurs between two or more different candidate sequences, then soft bit classification may be used to make the final selection.
The first bit value encoded by the selected best match sequence is selected as the decoded bit value. A confidence is also calculated for the decoded bit as a function of the confidences for each peak that makes up the decoded bit. Using the earlier example, assuming that the sequence was the best match, the decoded bit value would be a zero. The decoded bit confidence is a function of the confidence that the first peak is of type 1, and the confidence that the second peak is of type 0. After each bit is decoded, the window is moved forward by one bit (either one or two peaks depending on the value of the decoded bit).
According to another important feature of the invention, bit decoding may be performed in reverse time sequence after a stop event, or other signal impairment, in order to improve bit confidences. After a signal impairment, bit level confidences may drop to low values, even in areas where peak level confidences are high, if the bit level decoding loses synchronization with the encoded bit sequence. In this case, a xe2x80x9cbit reverse gap closurexe2x80x9d algorithm is applied. Bits are decoded, using one of the algorithms described earlier; analysis proceeds in reverse time sequence from an area of high bit level confidence until the area of the impairment is reached. A further aspect is that, after delineation of the low confidence region at the bit level, an adaptation to the bit classification algorithm may be used to advantage. The peaks in the low confidence region may be re-evaluated using the soft bit classification algorithm where only peak sequences which both start and end on a bit cell boundary are considered (referred to as xe2x80x9cconstrained bit classificationxe2x80x9d). The low confidence region defined at the bit level is used to identify the last confident bit boundary peak before the region (last peak of the last high confidence bit). Similarly, the first peak of the first high confidence bit after the low confidence region is used to identify the first confident bit boundary peak after the region. All legal peak class sequences equal in length to peak sequence in the low confidence region are then examined, with the additional constraint that only sequences both starting and ending on a bit boundary be considered.
According to another important feature of the invention, the decoded sequence of bit values may be divided into sub-sequences containing bits that have been decoded with high confidence. These sub-sequences are separated from each other by sub-sequences of bits that have been decoded with relatively low confidence. An examination of each of the high confidence bit sub-sequences is performed to identify the character level boundaries within the bit sub-sequence. Common magnetic stripe encoding standards (ABA, IATA) include the concept of a character that includes a character level parity bit. Given that all of the bits in the considered bit sub-sequence have been decoded with high confidence, only character alignments (one is possible per bit contained in the character) which satisfy the parity constraint are possible. By examining the legal character alignments in the bit sub-sequences before and after a low confidence sub-sequence (typically one per bit sub-sequence), a decoding error within the low confidence sub-sequence may be detected if the character alignment is not maintained across the region. The specific error detected is one of decoding either a greater or smaller number of bits than the correct number. In a manner similar to that described earlier for xe2x80x9cconstrained bit classificationxe2x80x9d, the low confidence region may be re-classified where the peaks in the region are decoded with the further constraint that a known number of bits are to be decoded. This is soft bit classification over a window of peaks equal to the number of peaks in the low confidence region (including bit boundary peaks), where only legal sequences that code the required number of bits are considered.
When the motion of the stripe temporarily reverses during a read, the result is referred to as a reversal event. Bit sequences are analysed to detect reversal events. These events are detected in numerous of ways, including comparing a total number of bits obtained from the analysis with an expected total number of bits. When the former exceeds the latter, a reversal event has occurred. The determination that a reversal may have occurred may also be made and confirmed through the analysis of the reverse time correlation between bit strings before and after stop events that invariably separate the bit sequences read before and after the change of stripe direction. In a typical practical case, the motion of the stripe changes directions twice. The bit sequence read in-between the two stop events is a repeat, in reverse time order, of the end of the bit sequence leading into the first stop event. Likewise, it is also a repeat of the beginning of the bit sequence leading away from the second stop event. During a read in which the stripe is entirely moved passed the read head, a reversal of direction implies that some sequence of bits is being read not only once, but at least three times. This fact may be used to advantage in obtaining a higher confidence bit classification for these bits on the stripe through correlation of the information from the three read passes. Optionally, a means for determining strip position or direction may be used to detect the occurrence of a reversal event.